import java.util.*;
class Solution {
        public int largestRectangleArea(int[] heights) {
            int len=heights.length;
            Stack<Integer> stack=new Stack<>();
            int answer=0;
            for(int i=0;i<len;i++){
                if(stack.empty()||heights[stack.peek()]<=heights[i]){
                    stack.push(i);
                }else{
                    int tmp=-1;
                    while(!stack.empty()&&heights[stack.peek()]>heights[i]){
                        tmp=stack.pop();
                        answer=Math.max(answer,(i-tmp)*heights[tmp]);
                    }
                    heights[tmp]=heights[i];
                    stack.push(tmp);
                }
            }
            while(!stack.empty())	{
                int top = stack.pop();
                answer = Math.max(answer, (len - top) * heights[top]);
            }
            return answer;
        }
    public boolean exist(char[][] board, String word) {
            char[] words=word.toCharArray();
            for(int i=0;i<board.length;i++){
                for(int j=0;j<board[0].length;j++){
                    if(dfs( words,board,i,j,0)){
                        return true;
                    }
                }
            }
            return false;
        }
        public boolean dfs( char [] words,char[][] board,int i,int j,int index){
            if(i>=board.length||i<0||j>=board[0].length||j<0||board[i][j]!=words[index]){
                return false;
            }
            if(index==words.length-1){
                return true;
            }
            board[i][j]='1';//表示此元素已经被访问过
            boolean res=dfs(words,board,i+1,j,index+1)
                    ||dfs(words,board,i-1,j,index+1)
                    ||dfs(words,board,i,j-1,index+1)
                    ||dfs(words,board,i,j+1,index+1);
            board[i][j]=words[index];//还原当前矩阵元素
            return res;
        }
    public boolean canPartition(int[] nums) {
        int len=nums.length;
        if(len==0){
            return false;
        }
        int sum=0;
        for(int i=0;i<len;i++){
            sum=sum+nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        int target=sum/2;
        Arrays.sort(nums);
        if(nums[0]>target){
            return false;
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        int val=0;
        int min=nums[0];
        for(int i=0;i<len;i++){
            int tmp=target-nums[i];
            if(map.containsKey(tmp)||tmp==0){
                return true;
            }else{
                while(map.containsValue(tmp-min)){
                    return true;
                }
                val=val+nums[i];
                map.put(val,nums[i]);
            }
        }
        return false;
    }

    public String minWindow(String s, String t) {
        int len=s.length();
        int len1=t.length();
        if(len==0||len1==0){
            return "";
        }
        int left=0;
        int right=1;
        int minStart=0;
        int minlen=len;
        while(left<right&&right<len){
            String ret=s.substring(left,right+1);
            int i=0;
            for(;i<len1;i++){
                if(!ret.contains(Character.toString(t.charAt(i)))){
                    break;
                }
            }
            if(i==len1){
                if(right-left+1<minlen){
                    minStart=left;
                    minlen=right-left+1;
                    left++;
                }
            }else{
                right++;
            }
        }
        return s.substring(minStart+1,minStart+minlen+1);
    }
}